package leetcode.code1671;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int minimumMountainRemovals(int[] nums) {
		int n = nums.length;
		int L = 0;
		while (L + 1 < n && nums[L + 1] <= nums[L]) {
			L++;
		}
		int R = n - 1;
		while (R - 1 >= 0 && nums[R - 1] <= nums[R]) {
			R--;
		}
		int size = R - L + 1;
		int[] left = new int[n];
		for (int i = L; i <= R; i++) {
			int d = i;
			for (int j = i - 1; j >= L; j--) {
				if (nums[i] > nums[j]) {
					d = Math.min(d, i - j - 1 + left[j]);
				}
			}
			left[i] = d;
		}
		int[] right = new int[n];
		for (int i = R; i >= L; i--) {
			int d = n - 1 - i;
			for (int j = i + 1; j <= R; j++) {
				if (nums[i] > nums[j]) {
					d = Math.min(d, j - i - 1 + right[j]);
				}
			}
			right[i] = d;
		}
		int ans = 10000;
		for (int i = L; i <= R; i++) {
			ans = Math.min(ans, left[i] + right[i]);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(6, this.minimumMountainRemovals(H.str2array3("[100,92,89,77,74,66,64,66,64]")));
		H.compare(2, this.minimumMountainRemovals(H.str2array3("[9,8,1,7,6,5,4,3,2,1]")));
		H.compare(3, this.minimumMountainRemovals(H.str2array3("[2,1,1,5,6,2,3,1]")));
		H.compare(0, this.minimumMountainRemovals(H.str2array3("[1,3,1]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
